---
title: "机器人塔"
created: 2025-11-28
tags:
  - 算法
---

# 机器人塔

## 题目 [机器人塔](https://www.lanqiao.cn/paper/3863/problem/118/)

![[image-70d70a7f.png]]

## 思路分析

感觉是dp 但是状态表示什么的暂时没头绪

但是又有点像递推里的那个费解的开关

好像确定了一排后 其他的也确定了 所以能否枚举最底下一排的状态？

![[image-2ea303d8.png]]

问题转变成了 二进制枚举底层情况 （从0~n） 然后根据底层情况做异或递推出上层情况

若最终满足 A、B个数满足 且推到了顶层 说明方案加1

**up = (cur ^ (cur >> 1)) & ((1 << (clv - 1)) - 1)**

如：cur=22（二进制位10110），clv为6

1、cur >> 1：将cur右移一位，右移一位为1011；

     1 << (clv - 1）：1向左移动clv-1位，为01111

2、 (cur ^ (cur >> 1))：求上一层的情况，但最左边多出来一位

![[2ad1047976364ea3b191419acaaca2c1-8aaf22bb.png]]

3、& ((1 << (clv - 1)) - 1)：和一个二进制位为01111相与（&）就能去掉最左边的一位。

注意“-”的优先级大于“>>”，所以需要加一个括号让<<先算。

抽丝剥茧下 发现和二进制有很大关系 所以 画模型很重要！

## 代码实现

```typescript
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

unordered_map<int,int> tier;

bool dfs(const bitset<32>& cur, int clv, int m, int n) {//cur:当前情况 clv:当前层数 m:A的剩余数量 n:B的剩余数量
    if (m < 0 || n < 0)
		return false;
    if (clv == 0)
		return m == 0 && n == 0;

    int cb = cur.count();//计算这一层1的个数
    int ca = clv - cb;//0就是当前层的数量减去1的数量 前导0无关
    m -= ca;
    n -= cb;
    bitset<32> mask((1 << (clv - 1)) - 1);
    bitset<32> up = (cur ^ (cur >> 1)) & mask;  // 算出上一层的状态
    return dfs(up, clv - 1, m, n);
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int A,B;
	cin>>A>>B;
	//M,N<500 最多1000人
	for(int i=1;i*(i+1)<2000;i++){
		tier[i*(i+1)/2]=i;
	}
	int level=tier[A+B];

	int res=0;
	for(int i=0;i<(1<<level);i++){
		if (dfs(bitset<32>(i), level, A, B)) {
            res++;
        }
	}
	cout<<res<<endl;
	return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[棋子换位|棋子换位]] 🏠 [[00-冲刺国赛]] ➡️ [[广场舞|广场舞]]